#include <stdio.h>
#define N 50

int data[N][N];
int dp[N][N];
int n;
int init_data();
int dp_findMaxPath();
int result_print();

int main(int argc, const char** args) {
	printf("tower's layers(<=50): ");
	scanf("%d", &n);

	init_data();
	dp_findMaxPath();
	result_print();

	return 0;
}

int init_data() {
	int i, j;
	printf("=====the num of eyery layer: =====\n");
	for (i = 0; i < n; ++i) {
		printf("%dth layer: ", i+1);
		for (j = 0; j <= i; ++j) {
			scanf("%d", &data[i][j]);
		}
	}
	printf("==============TOWER===============\n");
	for (i = 0; i < n; ++i) {
		for (j = 0; j <= i; ++j) {
			printf("%-3d ", data[i][j]);
		}
		printf("\n");
	}

	return 0;
}

int dp_findMaxPath() {
	int i, j;
	int max_node = 0;
	for (i = n-1, j = 0; j < n; ++j) {
		dp[i][j] = data[i][j];
	}

	for (i = n - 2; i >= 0; --i) {
		for (j = 0; j <= i; ++j) {
			max_node = dp[i+1][j] > dp[i+1][j+1] ? dp[i+1][j] : dp[i+1][j+1];
			dp[i][j] = max_node + data[i][j];
		}
	}

	return 0;
}

int result_print() {
	int i, j;
	int current_value;
	printf("==============RESULT==============\n");
	printf("path max sum: %d\n", dp[0][0]);
	printf("path: ");
	printf("%d", data[0][0]);
	for (i = 1, j = 0; i < n; ++i) {
		current_value = dp[i - 1][j] - data[i - 1][j];
		if (current_value == dp[i][j+1]) ++j;
		printf("->%d", data[i][j]);
	}
	printf("\n");

	return 0;
}